/*
题目链接：https://leetcode.cn/problems/minimum-time-to-complete-trips/description/
题目：2187.完成旅途的最少时间
提交时间：2024.9.16
二分，最少时间
*/

class Solution {
public:
    vector<int>t;
    long long total;
    long long minimumTime(vector<int>& time, long long totalTrips) {
        sort(time.begin(),time.end());
        for(long long i=0;i<time.size();i++) t.push_back(time[i]);
        total=totalTrips;
        long long l=1,r=time[time.size()-1]*(long long)totalTrips;        //表示花费最小时间（下界）和最大时间（上界）
        while(l<r){
            long long mid=l+(r-l)/2;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
    long long check(long long m){          //注意数据范围为long long
        long long sum=0;   //统计在m时间下，公交车走的趟数
        for(auto x:t){
            sum+=(m/x);
        }
        return sum>=total;
    }
};